package middle;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 根据 逆波兰表示法，求表达式的值。
 *
 * 有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 *
 * 注意两个整数之间的除法只保留整数部分。
 *
 * 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 *
 * 链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class EvaluateReversePolishNotation {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.evalRPN(new String[]{"4","13","5","/","+"});
    }
    /**
     * 15:13 ~ 16:19  1h 6min
     * */
    static class Solution {
        public int evalRPN(String[] tokens) {
            Deque<Integer> stack = new LinkedList<>();
            for(String s : tokens){
                if(isNumber(s)){
                    stack.push(Integer.parseInt(s));
                }else{
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    switch (s){
                        case "+": stack.push(num2 + num1); break;
                        case "-": stack.push(num2 - num1); break;
                        case "*": stack.push(num2 * num1); break;
                        case "/": stack.push(num2 / num1); break;
                    }
                }
            }
            return stack.pop();
        }

        private boolean isNumber(String s){
            return !("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s));
        }
    }
}
